Introduction

• A linear Diophantine equation is an equation of the form $$ax + by = c$$ where
  • $a$, $b$, and $c$ are integers
  • $x$ and $y$ are unknown integers
• These equations appear in many places:
  • dividing things into groups
  • scheduling and timing problems
  • puzzles and number tricks
• The Bézout Identity tells us how to write $\gcd(a,b)$ as a combination of $a$ and $b$.
• Now we use that identity to understand when equations like $ax + by = c$ have solutions — and how to find them.

What Is a Linear Diophantine Equation?

• A Diophantine equation is simply an equation where the solutions must be integers.
• A linear Diophantine equation has:
  • no powers
  • no fractions
  • just $ax + by = c$
• Examples:
  • $4x + 6y = 14$
  • $9x - 5y = 1$
  • $2x + 3y = 5$
• The key question:
  Does this equation have integer solutions?

This is where the gcd becomes essential.

When Does an Equation \(ax + by = c\) Have Solutions?

A fundamental fact:

• The equation $ax + by = c$ has integer solutions if and only if
• $$\gcd(a,b) \mid c.$$

Meaning:

• Let $d = \gcd(a,b)$.
• If $d$ divides $c$, solutions exist.
• If $d$ does not divide $c$, there are no integer solutions.

Why this is true:

• From Bézout’s Identity, $$ax_0 + by_0 = d.$$
• If $c$ is a multiple of $d$, say $c = kd$, then $$a(kx_0) + b(ky_0) = c.$$
• If $c$ is not a multiple of $d$, no combination of $a$ and $b$ can ever reach $c$.

This gives us a simple test before doing any work.

Finding One Particular Solution

Once we know solutions exist, we need one solution $(x_0, y_0)$.

Steps:

1. Compute $d = \gcd(a,b)$.
2. Use the extended Euclidean algorithm to find integers $u$ and $v$ such that $$au + bv = d.$$
3. Scale both coefficients by $c/d$: $$x_0 = u \cdot \frac{c}{d}, \qquad y_0 = v \cdot \frac{c}{d}.$$

This gives a valid solution to $ax + by = c$.

Example:

• Solve $4x - 7y = 5$.
• Extended Euclid gives $$4(2) + (-7)(1) = 1.$$
• Scaling these by $5/1$ gives $$4(10) + (-7)(5) = 5$$
• So $(x_0, y_0) = (10, 5)$ is a particular solution.

The General Solution: All Integer Solutions

Once we have one solution $(x_0, y_0)$, we can find all solutions.

Let:

• $d = \gcd(a,b)$
• Step vector: $$s_x = \frac{b}{d}, \qquad s_y = -\frac{a}{d}$$

Then every solution has the form: $$x = x_0 + s_x t, \qquad y = y_0 + s_y t$$ where $t$ is any integer.

Interpretation:

• Solutions form a family or line of integer points.
• Changing $t$ moves you along that line.

Example:

• For $4x - 7y = 5$, we found $(10,5)$.
• Since $d=1$, $$s_x = -7, \qquad s_y = -4.$$
• So $$x = 10 - 7t,\qquad y = 5 - 4t.$$

We can rewrite this in a “nicer” form by shifting $t$: $$x = 3 + 7t,\qquad y = 1 + 4t.$$

Special and Degenerate Cases

Case 1: $a = 0$

• Equation becomes $by = c$.
• Solutions exist only if $b \mid c$.
• Then $y = c/b$ and $x$ is free.

Case 2: $b = 0$

• Equation becomes $ax = c$.
• Solutions exist only if $a \mid c$.
• Then $x = c/a$ and $y$ is free.

Case 3: $c = 0$

• Equation is $ax + by = 0$.
• Always solvable.
• Solutions form a line through the origin: $$x = \frac{b}{d}t,\qquad y = -\frac{a}{d}t.$$

These cases are simpler but follow the same principles.

Applications and Connections

Linear Diophantine equations appear in many places:

• Finding modular inverses
  • e.g., solving $ax \equiv 1 \pmod{m}$
• Scheduling problems
  • e.g., when two repeating events coincide
• Integer partitioning
  • e.g., can you make exactly $c$ using coins of sizes $a$ and $b$?
• Number puzzles
  • classic “chicken and rabbit” type problems

Summary and Key Ideas

• A linear Diophantine equation is $ax + by = c$ with integer solutions.
• Solutions exist iff $\gcd(a,b)$ divides $c$.
• The extended Euclidean algorithm gives one solution.
• All solutions form a family: $$x = x_0 + \frac{b}{d}t,\qquad y = y_0 - \frac{a}{d}t.$$
• The geometry is simple: integer points on a line.

Calculator

Exercises

1. Determine whether $6x + 9y = 15$ has integer solutions.
   • If yes, find one.

   Solution

   Equation: $6x + 9y = 15$

   • $\gcd(6,9) = 3$, and $3 \mid 15$ → solutions exist.
   • Divide whole equation by $3$: $$2x + 3y = 5.$$
   • Try $x = 1$: $$2(1) + 3y = 5 \Rightarrow 3y = 3 \Rightarrow y = 1.$$

   One solution: $(x_0,y_0) = (1,1)$.

   General solution (optional):

   • Here $d = \gcd(2,3)=1$, so $$x = 1 + 3t,\quad y = 1 - 2t.$$
2. Solve $4x + 6y = 14$.
   • Find one solution and then the general solution.

   Solution

   Equation: $4x + 6y = 14$

   • $\gcd(4,6) = 2$, and $2 \mid 14$ → solutions exist.
   • Divide by $2$: $$2x + 3y = 7.$$
   • Try $x = 2$: $$2(2) + 3y = 7 \Rightarrow 4 + 3y = 7 \Rightarrow 3y = 3 \Rightarrow y = 1.$$

   One solution: $(x_0,y_0) = (2,1)$.

   General solution:

   • $d = \gcd(4,6) = 2$, so $$s_x = \frac{6}{2} = 3,\quad s_y = -\frac{4}{2} = -2.$$
   • Thus $$x = 2 + 3t,\quad y = 1 - 2t.$$
3. Find all integer solutions to $9x - 5y = 1$.

   Solution

   Equation: $9x - 5y = 1$

   • $\gcd(9,5) = 1$ → solutions exist.
   • Use small trial: try $x = 1$: $$9(1) - 5y = 1 \Rightarrow 9 - 5y = 1 \Rightarrow 5y = 8 \Rightarrow y = \frac{8}{5} \text{ (not integer)}.$$
   • Try $x = 2$: $$18 - 5y = 1 \Rightarrow 5y = 17 \Rightarrow y = \frac{17}{5}.$$
   • Try $x = -1$: $$-9 - 5y = 1 \Rightarrow -5y = 10 \Rightarrow y = -2.$$

   So $(x_0,y_0) = (-1,-2)$ is a solution.

   General solution:

   • $d = 1$, so $$s_x = \frac{-5}{1} = -5,\quad s_y = -\frac{9}{1} = -9.$$
   • Thus $$x = -1 - 5t,\quad y = -2 - 9t.$$

   You can also shift $t$ to get a “nicer” form if desired.

4. Does the equation $8x + 12y = 7$ have integer solutions?
   • Explain why or why not.

   Solution

   Equation: $8x + 12y = 7$

   • $\gcd(8,12) = 4$.
   • $4 \nmid 7$ → $7$ is not a multiple of $4$.

   Conclusion: No integer solutions.

5. Solve $21x + 14y = 7$.
   • Give the general solution.

   Solution

   Equation: $21x + 14y = 7$

   • $\gcd(21,14) = 7$, and $7 \mid 7$ → solutions exist.
   • Divide by $7$: $$3x + 2y = 1.$$
   • Try $x = 1$: $$3(1) + 2y = 1 \Rightarrow 3 + 2y = 1 \Rightarrow 2y = -2 \Rightarrow y = -1.$$

   So $(x_0,y_0) = (1,-1)$ is a solution.

   General solution:

   • $d = \gcd(21,14) = 7$, so $$s_x = \frac{14}{7} = 2,\quad s_y = -\frac{21}{7} = -3.$$
   • Thus $$x = 1 + 2t,\quad y = -1 - 3t.$$
6. Find one solution to $35x + 22y = 1$.
   • Then write the full family of solutions.

   Solution

   Equation: $35x + 22y = 1$

   • $\gcd(35,22) = 1$ → solutions exist.
   • Use extended Euclid (compressed):
     • One Bézout identity is $$1 = 35(19) + 22(-30).$$

   So $(x_0,y_0) = (19,-30)$ is a solution.

   General solution:

   • $d = 1$, so $$s_x = \frac{22}{1} = 22,\quad s_y = -\frac{35}{1} = -35.$$
   • Thus $$x = 19 + 22t,\quad y = -30 - 35t.$$
7. Solve $2x + 3y = 5$ and express the general solution in the “nicest” form you can.

   Solution

   Equation: $2x + 3y = 5$

   • $\gcd(2,3) = 1$ → solutions exist.
   • Try $x = 1$: $$2(1) + 3y = 5 \Rightarrow 3y = 3 \Rightarrow y = 1.$$

   So $(x_0,y_0) = (1,1)$ is a solution.

   General solution:

   • $d = 1$, so $$s_x = 3,\quad s_y = -2.$$
   • Thus $$x = 1 + 3t,\quad y = 1 - 2t.$$

   This is already a very “nice” form.

8. Special case: solve $0x + 9y = 27$.
   • What does the solution set look like?

   Solution

   Equation: $0x + 9y = 27$

   • This simplifies to $9y = 27$.
   • So $y = 3$.
   • $x$ is free (any integer).

   Solution set: $$x = t,\quad y = 3,\quad t \in \mathbb{Z}.$$

9. Solve $ax + by = 0$ for $a=12$, $b=18$.
   • Give the general solution.

   Solution

   Equation: $12x + 18y = 0$

   • $\gcd(12,18) = 6$.
   • We can factor out $6$: $$6(2x + 3y) = 0 \Rightarrow 2x + 3y = 0.$$
   • Solve $2x + 3y = 0$:
     • Let $y = 2t$ → then $2x + 3(2t) = 0 \Rightarrow 2x + 6t = 0 \Rightarrow x = -3t$.

   So: $$x = -3t,\quad y = 2t,\quad t \in \mathbb{Z}.$$ This matches the general pattern $$x = \frac{b}{d}t,\quad y = -\frac{a}{d}t$$ with $a=12$, $b=18$, $d=6$.